package leetcode.array.sum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 18. 四数之和
 *
 */
public class FourSum {
    public static void main(String[] args) {
        FourSum solution = new FourSum();

        // 示例数据
        int[] nums = {1, 0, -1, 0, -2, 2};

        // 开始时间
        long start = System.currentTimeMillis();
        List<List<Integer>> resList = solution.fourSum(nums, 0);
        System.out.println(resList);

        // 结束时间
        long end = System.currentTimeMillis();
        System.out.println("花费时间(毫秒): " + (end - start));
    }


    /**
     * 不重复的四元组
     * @param nums      数组
     * @param target    目标值
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int zero = 0; zero < len - 3; zero++) {
            if (zero > 0 && nums[zero] == nums[zero - 1]) {
                continue;
            }
            for (int first = zero + 1; first < len - 2; first++) {
                if (first > zero + 1 && nums[first] == nums[first - 1]) {
                    continue;
                }
                int third = len - 1;
                for (int second = first + 1; second < len - 1; second++) {
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
                        continue;
                    }
                    while (second < third && (nums[zero] + nums[first] + nums[second] + nums[third] > target)) {
                        third--;
                    }
                    if (second == third) {
                        break;
                    }
                    if (nums[zero] + nums[first] + nums[second] + nums[third] == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[zero]);
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        ans.add(list);
                    }
                }
            }
        }
        return ans;
    }


}
